def word_search(board, target):
    m = len(board)
    n = len(board[0])

    for i in range(m):
        for j in range(n):
            if board[i][j] == target[0]:
                res = dfs(board, target, m, n, i, j, 0)
                if res:
                    return True

    return False


def dfs(board, target, m, n, i, j, pos):
    if pos == len(target):
        return True
    if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != target[pos]:
        return False
    board[i][j] = '*'
    res = False
    if dfs(board, target, m, n, i + 1, j, pos + 1) or dfs(board, target, m, n, i - 1, j, pos + 1) or dfs(board, target,
                                                                                                         m, n, i, j + 1,
                                                                                                         pos + 1) or dfs(
        board, target, m, n, i, j - 1, pos + 1):
        res = True
    board[i][j] = target[pos]
    return res


board =[
    ['A', 'B', 'C', 'E'],
    ['S', 'F', 'C', 'S'],
    ['A', 'D', 'E', 'E']
]

print(word_search(board, "ABCCED"))
print(word_search(board, "SEE"))
print(word_search(board, "ABCB"))
